A
弱智题,不断用 除以 即可。
#include <cstdio>
int k, l, cnt;
int main() {
scanf("%d%d", &k, &l);
while (l % k == 0) cnt++, l /= k;
if (l == 1) printf("YES\n%d\n", cnt - 1);
else puts("NO");
}
B
看到数据范围 考虑状压,直接暴力枚举子集判断是否有冲突即可。
时间复杂度 。
Code
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 20;
string s[N], a, b;
int f[N][N], n, m, ans;
int find(string str) {
int i = 0;
while (str != s[i]) i++;
return i;
}
int popcount(int x) {
int ret = 0;
while (x) ret += x & 1, x >>= 1;
return ret;
}
int main() {
cin >> n >> m;
for (int i = 0; i <= n - 1; i++) cin >> s[i];
sort(s, s + n);
for (int i = 1; i <= m; i++) {
cin >> a >> b;
int u = find(a), v = find(b);
f[u][v] = f[v][u] = 1;
}
for (int s = 0; s <= (1 << n) - 1; s++) {
int flag = 0;
for (int i = 0; i <= n - 1; i++) {
if ((s >> i & 1) == 0)
continue;
for (int j = i + 1; j <= n - 1; j++) {
if ((s >> j & 1) == 0)
continue;
flag |= f[i][j];
if (flag) break;
}
if (flag) break;
}
if (flag == 0) {
if (popcount(s) > popcount(ans))
ans = s;
}
}
cout << popcount(ans) << endl;
for (int i = 0; i <= n - 1; i++) {
if (ans >> i & 1)
cout << s[i] << endl;
}
}
C
大模拟,不知道为什么死活写不对。
搬一个题解代码。
Code
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
char s[N], word[N];
int type[N], tp, p, flag, cnt, len, t;
int modify() {
int l = strlen(word);
if (l < 3) return 0;
if (strcmp(word + l - 4, "lios") == 0) return 1;
if (strcmp(word + l - 5, "liala") == 0) return -1;
if (strcmp(word + l - 3, "etr") == 0) return 2;
if (strcmp(word + l - 4, "etra") == 0) return -2;
if (strcmp(word + l - 6, "initis") == 0) return 3;
if (strcmp(word + l - 6, "inites") == 0) return -3;
return 0;
}
int main() {
cin.getline(s, N);
flag = 1;
len = strlen(s);
for (int i = 0; i <= len; i++) {
if (s[i] != ' ' && s[i] != '\0')
word[p++] = s[i];
else {
word[p] = '\0';
cnt++;
t = modify();
if (t != 0) type[tp++] = t;
else {
flag = 0;
break;
}
}
}
if (cnt == 1 && flag == 1) {
puts("YES");
return 0;
}
if (flag == 0) {
puts("NO");
return 0;
}
cnt = 0;
for (int i = 0; i < tp; i++) {
if (abs(type[i]) == 2)
cnt++;
}
if (cnt != 1) {
puts("NO");
return 0;
}
flag = 1;
if (type[0] < 0) {
for (int i = 1; i < tp; i++)
if (type[i] > 0) {
flag = 0;
break;
}
}
else {
for (int i = 1; i < tp; i++)
if (type[i] < 0) {
flag = 0;
break;
}
}
if (flag == 0) {
puts("NO");
return 0;
}
flag = 1;
for (int i = 1; i < tp; i++) {
if (abs(type[i]) < abs(type[i - 1])) {
flag = 0;
break;
}
}
if (flag) puts("YES");
else puts("NO");
}
<!-- more -->
D
考虑字符串哈希。找出 和 在 中出现的位置,暴力枚举端点,对哈希值去重即可。
时间复杂度 。
#include <cstdio>
#include <cstring>
#include <vector>
#include <unordered_set>
const int N = 2005;
const int base = 131;
char be[N], ed[N], s[N];
std::vector<int> p, q;
typedef unsigned long long uint64;
uint64 hash[N], Pow[N], f, g;
std::unordered_set<uint64> st;
uint64 getHash(int x, int l) {
return hash[x] - hash[x + l] * Pow[l];
}
int main() {
scanf("%s%s%s", s, be, ed);
int n = strlen(s);
int m = strlen(be);
int k = strlen(ed);
Pow[0] = 1;
for (int i = 1; i < N; i++) Pow[i] = Pow[i - 1] * base;
hash[n] = 0;
for (int i = n - 1; i >= 0; i--) hash[i] = hash[i + 1] * base + s[i];
for (int i = m - 1; i >= 0; i--) f = f * base + be[i];
for (int i = k - 1; i >= 0; i--) g = g * base + ed[i];
for (int i = 0; i + m <= n; i++) {
if (getHash(i, m) == f)
p.push_back(i);
}
for (int i = 0; i + k <= n; i++) {
if (getHash(i, k) == g)
q.push_back(i + k - 1);
}
int ans = 0;
for (int i: p) for (int j: q) {
int l = j - i + 1;
if (i <= j && l >= std::max(m, k)) {
uint64 val = getHash(i, l);
if (!st.count(val)) ans++, st.insert(val);
}
}
printf("%d\n", ans);
}
E
注意到
所以只需判断素数是否模 余 。
由于CF的测评机跑得特别快可以暴力筛出 以内的所有素数,依次枚举即可。
注意数组开不下,需要使用 bitset。
时间复杂度 。
Code
#include <iostream>
#include <cstdio>
#include <bitset>
const int N = 3e8 + 5;
const int M = 2e7 + 5;
std::bitset<N> vis;
int prime[M], l, r, cnt, ans;
inline void sieve() {
for (int i = 2; i <= r; i++) {
if (!vis[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] <= r; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
scanf("%d%d", &l, &r);
sieve();
for (int i = 1; i <= cnt; i++) {
if (prime[i] < l) continue;
if (prime[i] % 4 == 1) ans++;
}
printf("%d\n", ans + (l <= 2 && r >= 2));
return 0;
}